#include <bits/stdc++.h>
using namespace std;

#define FOR_INC(i, start, end) for (int i = start; i < end; ++i)
#define FOR_DEC(i, start, end) for (int i = start; i > end; --i)
#define FOR_INC_EQUAL(i, start, end) for (int i = start; i <= end; ++i)
#define FOR_DEC_EQUAL(i, start, end) for (int i = start; i >= end; --i)
#define int long long
//class UnionFind{
//public:
//    vector<int> parent;
//    int count;
//    explicit UnionFind(int n){
//        count = n;
//        for(int i=0;i<n;i++){
//            this->parent.emplace_back(i);
//        }
//    }
//
//    void union1(int x,int y){
//        int p = find(x);
//        int q = find(y);
//        if(p==q){
//            return;
//        }
//        this->count--;
//        this->parent[p] = q;
//    }
//
//    int find(int index){
//        if(this->parent[index]!=index){
//            this->parent[index] = find(this->parent[index]);
//        }
//        return index;
//    }
//};
//
//class Fenwick {
//    vector<int> f;
//
//public:
//    Fenwick(int n) : f(n) {}
//    inline static int lowBit(int n){
//        return n&-n;
//    }
//    void update(int i, int val) {
//        for (; i < f.size(); i += lowBit(i)) {
//            f[i] += val;
//        }
//    }
//
//    int query(int i) {
//        int res = 0;
//        for (; i > 0; i -= lowBit(i)) {
//            res += f[i];
//        }
//        return res;
//    }
//
//    void add(int i,int val){
//        f[i]+=val;
//    }
//
//    int get(int index){
//        return f[index];
//    }
//};
//
//void getNums(const string& s){
//    string t;
//    for (char i : s) {
//        if(i=='['){
//            t+='{';
//        }else if(i==']'){
//            t+='}';
//        }else{
//            t+=i;
//        }
//    }
//    cout<<t<<endl;
//}
//
//class Solution {
//public:
//
//};
//
//int fastpow(int base,int n,int mod){
//    int ans = 1;
//    while(n>0){
//        if((n&1)==1){
//            ans = (ans*base)%mod;
//        }
//        n>>=1;
//        base = (base*base)%mod;
//    }
//    return ans;
//}

int a[100],b[100],c[100],d[100];
//a数组表示的是行；
//b数组表示的是列；
//c表示的是左下到右上的对角线；
//d表示的是左上到右下的对角线；
int total;//总数:记录解的总数
int n;//输入的数，即N*N的格子，全局变量，搜索中要用
void print1()
{
    if(total<=2)//保证只输出前三个解，如果解超出三个就不再输出，但后面的total还需要继续叠加
    {
        for(int k=1;k<=n;k++)
            cout<<a[k]<<" ";//for语句输出
        cout<<endl;
    }
    total++;//total既是总数，也是前三个排列的判断
}
void queen(int i)//搜索与回溯主体
{
    if(i>n)
    {
        print1();//输出函数，自己写的
        return;
    }
    else
    {
        for(int j=1;j<=n;j++)//尝试可能的位置
        {
            if((!b[j])&&(!c[i+j])&&(!d[i-j+n]))//如果没有皇后占领，执行以下程序
            {
                a[i]=j;//标记i排是第j个
                b[j]=1;//宣布占领纵列
                c[i+j]=1;
                d[i-j+n]=1;
                //宣布占领两条对角线
                queen(i+1);//进一步搜索，下一个皇后
                b[j]=0;
                c[i+j]=0;
                d[i-j+n]=0;
                //（回到上一步）清除标记
            }
        }
    }
}
signed main () {
//    vector<vector<int>> grid = {{0,0,1,1},{0,0,1,1},{0,2,1,3}};
//    vector<int> nums = {1,2,7};
//    Solution s;
//    vector<int> arr = {4,5,3};
//    s.minOperations(nums,arr);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    cin>>n;//输入N*N网格，n已在全局中定义
    queen(1);//第一个皇后
    cout<<total;//输出可能的总数
    return 0;
}
